﻿#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

/*
* 阶乘计算
* */
//int fact(int a)
//{
//	if (a==0)
//	{
//		return 1;
//	}
//	else {
//		return  a*fact(a - 1);
//	}
//}
//int main()
//{
//	int n = 0;
//	int jieguo = 0;
//	printf("请输入需要计算的阶乘：\n");
//	scanf("%d", &n);
//	jieguo =fact(n);
//	printf("\n结果为：%d\n", jieguo);
//
//	return 0;
//}


//顺序输出数字的每一位

//void print(int value)
//{
//	if (value>9)
//	{
//		//删掉最后一位
//		print(value / 10);
//	}
//	//输出当前的最后一位
//	printf(" %d", value % 10);
//}
//
//int main()
//{
//	int n = 0;
//	printf("请输入需要输出的数字：\n");
//	scanf("%d", &n);
//	print(n);
//
//	return 0;
//}

//斐波那契数列求解//递归法
//int fib(int value)
//{
//	if (value <= 2)
//	{
//		return 1;
//	}
//	else
//	{
//		return fib(value - 1) + fib(value - 2);
//	}
//}
////迭代法
//int fib(int value)
//{
//	int a = 1;
//	int b = 1;
//	int c = 0;
//	if (value <= 2)
//	{
//		return 1;
//	}
//	while (value>2)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//		value--;
//	}
//	return c;
//}
//求第50个斐波那契数列时可以明显感觉到递归的效率低下
//int main()
//{
//	int n = 0;
//	int value = 0;
//	printf("请输入需要计算第几个斐波那契数：\n");
//	scanf("%d", &n);
//	value=fib(n);
//	printf("第%d个斐波那契数：%d\n", n, value);
//	return 0;
//}


//int fangfa_number = 0;
//int  Frog_jumping_steps(int step)
//{
//	if (step == 0)
//	{
//		fangfa_number++;
//		return 1;
//	}
//	else if(step < 0)
//	{
//		return 0;
//	}
//		
//
//
//	return Frog_jumping_steps(step - 2) + Frog_jumping_steps(step - 1);
//
//
//}

//以上方法空间复杂度和时间复杂度都太大了可以用50试试
//题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
//int main()
//{
//	int n = 0;
//	int value = 0;
//	printf("请输入青蛙需要跳几级台阶？\t");
//	scanf("%d", &n);
//	//Frog_jumping_steps(n);
//	//printf("\n有%d种方式\n", fangfa_number);
//	//return 0;
//	Frog_jumping_steps(n);
//	printf("%d", fangfa_number);
//	return 0;
//}

/*
* 我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：

f(x)=f(x−1)+f(x−2)

它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解，因为每次只能爬 1 级或 2 级，所以 f(x) 只能从 f(x−1) 和 f(x−2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。

以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 0 级开始爬的，所以从第 0 级爬到第 0 级我们可以看作只有一种方案，即 f(0)=1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1)=1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下，根据转移方程得到 f(2)=2，f(3)=3，f(4)=5，……，我们把这些情况都枚举出来，发现计算的结果是正确的。

我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n) 的实现，但是由于这里的 f(x) 只和 f(x−1) 与 f(x−2) 有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。

作者：力扣官方题解
链接：https://leetcode.cn/problems/climbing-stairs/solutions/286022/pa-lou-ti-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

int main()
{
	int n = 0;
	int value = 0;
	printf("请输入青蛙需要跳几级台阶？\t");
	scanf("%d", &n);
	long long int p = 0, q = 0, r = 1;
	for (int i = 1; i <= n; ++i) {
		p = q;
		q = r;
		r = p + q;
	}
	printf("有%lld种跳法！", r);
	return 0;
}